329. Longest Increasing Path in a Matrix
Hard

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

 

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 231 - 1
Accepted
234,415
Submissions
499,492
Seen this question in a real interview before?
Companies

Average Rating: 4.85 (108 votes)

Premium

Overview

This article is for advanced readers. It introduces the following ideas: Depth First Search (DFS), Memoization, Dynamic programming, Topological Sorting. It explains the relation between dynamic programming and topological sorting.

Solution


Approach #1 (Naive DFS) [Time Limit Exceeded]

Intuition

DFS can find the longest increasing path starting from any cell. We can do this for all the cells.

Algorithm

Each cell can be seen as a vertex in a graph GG. If two adjacent cells have value a<ba < b, i.e. increasing then we have a directed edge (a,b)(a, b). The problem then becomes:

Search the longest path in the directed graph GG.

Naively, we can use DFS or BFS to visit all the cells connected starting from a root. We update the maximum length of the path during search and find the answer when it finished.

Usually, in DFS or BFS, we can employ a set visited to prevent the cells from duplicate visits. We will introduce a better algorithm based on this in the next section.

Complexity Analysis

  • Time complexity : O(2m+n)O(2^{m+n}). The search is repeated for each valid increasing path. In the worst case we can have O(2m+n)O(2^{m+n}) calls.

  • Space complexity : O(mn)O(mn). For each DFS we need O(h)O(h) space used by the system stack, where hh is the maximum depth of the recursion. In the worst case, O(h)=O(mn)O(h) = O(mn).


Approach #2 (DFS + Memoization) [Accepted]

Intuition

Cache the results for the recursion so that any subproblem will be calculated only once.

Algorithm

From previous analysis, we know that there are many duplicate calculations in the naive approach.

One optimization is that we can use a set to prevent the repeat visit in one DFS search. This optimization will reduce the time complexity for each DFS to O(mn)O(mn) and the total algorithm to O(m2n2)O(m^2n^2).

Here, we will introduce more powerful optimization, Memoization.

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

In our problem, we recursively call dfs(x, y) for many times. But if we already know all the results for the four adjacent cells, we only need constant time. During our search if the result for a cell is not calculated, we calculate and cache it; otherwise, we get it from the cache directly.

Complexity Analysis

  • Time complexity : O(mn)O(mn). Each vertex/cell will be calculated once and only once, and each edge will be visited once and only once. The total time complexity is then O(V+E)O(V+E). VV is the total number of vertices and EE is the total number of edges. In our problem, O(V)=O(mn)O(V) = O(mn), O(E)=O(4V)=O(mn)O(E) = O(4V) = O(mn).

  • Space complexity : O(mn)O(mn). The cache dominates the space complexity.


Approach #3 (Peeling Onion) [Accepted]

Intuition

The result of each cell only related to the result of its neighbors. Can we use dynamic programming?

Algorithm

If we define the longest increasing path starting from cell (i,j)(i, j) as a function

f(i,j) f(i, j)

then we have the following transition function

f(i,j)=max{f(x,y)(x,y) is a neighbor of(i,j) and matrix[x][y]>matrix[i][j]}+1 f(i, j) = max\{f(x, y)| (x, y)~\mathrm{is~a~neighbor~of} (i, j)~\mathrm{and} ~\mathrm{matrix}[x][y] \gt \mathrm{matrix}[i][j]\} + 1

This formula is the same as used in the previous approaches. With such transition function, one may think that it is possible to use dynamic programming to deduce all the results without employing DFS!

That is right with one thing missing: we don't have the dependency list.

For dynamic programming to work, if problem B depends on the result of problem A, then we must make sure that problem A is calculated before problem B. Such order is natural and obvious for many problems. For example the famous Fibonacci sequence:

F(0)=1,F(1)=1,F(n)=F(n1)+F(n2) F(0) = 1, F(1) = 1, F(n) = F(n - 1) + F(n - 2)

The subproblem F(n)F(n) depends on its two predecessors. Therefore, the natural order from 0 to n is the correct order. The dependent is always behind the dependee.

The terminology of such dependency order is "Topological order" or "Topological sorting":

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u,v)(u, v), vertex uu comes before vv in the ordering.

In our problem, the topological order is not natural. Without the value in the matrix, we couldn't know the dependency relation of any two neighbors A and B. We have to perform the topological sort explicitly as a preprocess. After that, we can solve the problem dynamically using our transition function following the stored topological order.

There are several ways to perform the topological sorting. Here we employ one of them called "Peeling Onion".

The idea is that in a DAG, we will have some vertex who doesn't depend on others which we call "leaves". We put these leaves in a list (their internal ordering does matter), and then we remove them from the DAG. After the removal, there will be new leaves. We do the same repeatedly as if we are peeling an onion layer by layer. In the end, the list will have a valid topological ordering of our vertices.

In out problem, since we want the longest path in the DAG, which equals to the total number of layers of the "onion". Thus, we can count the number of layers during "peeling" and return the counts in the end without invoking dynamic programming.

Complexity Analysis

  • Time complexity : O(mn)O(mn). The the topological sort is O(V+E)=O(mn)O(V+E) = O(mn). Here, VV is the total number of vertices and EE is the total number of edges. In our problem, O(V)=O(mn)O(V) = O(mn), O(E)=O(4V)=O(mn)O(E) = O(4V) = O(mn).

  • Space complexity : O(mn)O(mn). We need to store the out degrees and each level of leaves.


Remarks

  • Memoization: for a problem with massive duplicate calls, cache the results.
  • Dynamic programming requires the subproblem solved in topological order. In many problems, it coincides the natural order. For those who doesn't, one need perform topological sorting first. Therefore, for those problems with complex topology (like this one), search with memorization is usually an easier and better choice.

Report Article Issue

Comments: 54
jguodev's avatar
Read More

Who can help explain why the Time complexity of Approach 1 is O(2^(m+n))?
Thanks.

54
Show 25 replies
Reply
Share
Report
ghostfacechillah's avatar
Read More

"Usually, in DFS or BFS, we can employ a set visited to prevent the cells from duplicate visits. We will introduce a better algorithm based on this in the next section." but I did not find which part in the article explains why we don't have to maintain such a visited set. My guess is because the path is increasing, we will never visit a node with smaller value.

29
Show 6 replies
Reply
Share
Report
kiljaeden's avatar
Read More

I think it is worthy to mention that for most of this kind of questions that we could not add memorization upon a DFS. This question is a special case. Normally when you could move to 4 directions, there would be cycle so you could not memorize the result. However since this question is strictly increasing, thus it is a DAG.

19
Reply
Share
Report
jinchuan's avatar
Read More

the time complexity of the second solution should be O(mn) in total, isn't it?

22
Show 1 reply
Reply
Share
Report
haotianliu1801's avatar
Read More

Why do we have to increment ans by 1 at the end of DFS in solution #1?

5
Show 2 replies
Reply
Share
Report
hanzhoutang's avatar
Read More

It can also be a dp problem.
The idea is that we first update the dp matrix from top to down, left to right and then update it from bottom to top, right to left. We continue this procedure until dp matrix doesn't update. Here is my code:

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
        if(matrix[0].empty()) return 0;
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),1));
        int ret = 0;
        int oldvalue = 0;
        int updating = false;
        while(true){
        updating = false;
        for(int i=0;i<matrix.size();i++){
            for(int j = 0;j<matrix[0].size();j++){
                oldvalue = dp[i][j];
                if(i>=1&&matrix[i-1][j]<matrix[i][j]){
                    dp[i][j] = max(dp[i-1][j]+1 ,dp[i][j]);
                }
                if(j>=1&&matrix[i][j-1]<matrix[i][j]){
                    dp[i][j] = max(dp[i][j-1]+1,dp[i][j]);
                }
                if(oldvalue !=dp[i][j]){
                    updating = true;
                }
                ret = max(ret,dp[i][j]);
            }
        }
        for(int i= matrix.size()-1;i>=0;i--){
            for(int j = matrix[0].size()-1;j>=0;j--){
                oldvalue = dp[i][j];
                if(i<matrix.size()-1&&matrix[i+1][j]<matrix[i][j]){
                    dp[i][j] = max(dp[i+1][j]+1,dp[i][j]);
                }
                if(j<matrix[0].size()-1&&matrix[i][j+1]<matrix[i][j]){
                    dp[i][j] = max(dp[i][j+1]+1,dp[i][j]);
                }
                if(oldvalue != dp[i][j]){
                    updating = true;
                }
                ret = max(ret,dp[i][j]);
            }
        }       
            if(!updating){
                break;
            }
        }
        return ret;
    }

6
Show 2 replies
Reply
Share
Report
Kushina's avatar
Read More

Appreciate the Remarks summarizing the insights/take-aways from the solution. This should be made a more common practice, if possible. Many thanks!

3
Reply
Share
Report
harleyquinn's avatar
Read More

can you give more examples of questions where onion peeling is used for solving the question?

3
Show 3 replies
Reply
Share
Report
himani_01's avatar
Read More

According to me the complexity for approach 1 should be (4^mn)
How are we reaching to m+n factor here .. Since we can move in any of the 4 direction. I feel the longest path could be as long as m*n.

2
Show 1 reply
Reply
Share
Report
arijitp's avatar
Read More

In approach 1, for each vertex, we are doing work equivalent to O(2^(mn)) since the longest snake path consists of mn vertices. Now without memoization, this will be repeated across all mn vertices. So isn't the time complexity of approach 1 O(mn2^(mn)) ??

3
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/29/2021 11:46Accepted44 ms15.8 MBcpp
05/26/2021 15:42Accepted40 ms16 MBcpp
04/24/2021 09:35Accepted32 ms16.1 MBcpp
04/11/2021 07:53Accepted60 ms16.3 MBcpp
04/11/2021 07:47Accepted48 ms16.1 MBcpp
04/11/2021 07:47Accepted40 ms16.2 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.